Trong lúc sống lưu vong, Justinianos đã bắt đầu tính mưu kế và tập hợp những người ủng hộ nỗ lực giành lại ngôi vị hoàng đế.[15] Justinianos có nghĩa vụ phải tới Cherson và nhà chức trách quyết định trả ông trở về Constantinopolis vào năm 702 hoặc 703.[5] Nhân dịp đó ông trốn khỏi Cherson và nhận được sự giúp đỡ từ Ibusirus Gliabanus (Busir Glavan), khả hãn của người Khazar đón tiếp cựu hoàng một cách nhiệt tình và còn gả cô em gái của mình làm vợ nữa.[15] Justinianos bèn đổi tên vợ mới cưới thành Theodora theo tên của vợ Đại đế Justinianus I.[16] Họ được cấp một ngôi nhà ở thị trấn Phanagoria ngay lối vào biển Azov. Thế nhưng Busir được Tiberios mua chuộc tính giết người em rể, liền phái hai viên quan Khazar là Papatzys và Balgitzin tới hạ thủ.[17] Nhờ người vợ cảnh báo trước, Justinianos đã tự tay mình bóp cổ Papatzys và Balgitzin cho đến chết.[18] Rồi ông kiếm một chiếc thuyền đánh cá trở về Cherson, triệu tập toàn bộ phe cánh của mình lên thuyền đi về phía tây qua biển Đen.[19]

Ngay khi con tàu vừa rời bến thì Justinianos cho lái tàu dọc theo bờ biển phía bắc của Biển Đen, ông và thủy thủ đoàn của mình bỗng dưng bị cuốn vào một cơn bão ở đâu đó giữa cửa sông Dniester và sông Dnepr.[17] Trong lúc nó đương hoành hành, một trong những tên đồng đội tới chỗ Justinianos bảo rằng nếu cựu hoàng hứa với Chúa là mình sẽ tỏ ra cao thượng và không tìm kiếm sự trả thù khi trở lại ngai vàng thì mọi người mới được cứu rỗi.[19] Justinianos liền vặn lại, "Nếu ta tha cho một tên trong số chúng thì có thể Chúa sẽ dìm ta ngay tại đây".[17]

Sau khi vượt qua được cơn bão, Justinianos tiếp theo liền tiếp cận vua Tervel của Bulgaria.[19] Tervel đồng ý chu cấp tất cả sự hỗ trợ quân sự cần thiết cho Justiniano phục vị để đổi lấy những cân nhắc về tài chính, phần thưởng là một vương miện của Caesar và Justinianos phải gả cô con gái Anastasia cho mình.[15] Vào mùa xuân năm 705, Justinianos dẫn đầu một đội quân lên tới 15.000 người Bulgar và vài toán kỵ binh Slav tiến đến trước dãy tường thành của Constantinopolis.[15] Trong vòng ba ngày, Justinianos đã cố gắng thuyết phục dân chúng Constantinopolis mở cửa thành quy thuận nhưng không có kết quả.[20] Nhận thấy khó mà đoạt lấy thành phố bằng vũ lực, ông và một vài toán quân đã lén xâm nhập qua một đường ống dẫn nước chưa sử dụng dưới chân tường thành phố, khuấy động phe cánh ủng hộ của mình và chia nhau nắm quyền kiểm soát thành phố trong một cuộc đảo chính lúc nửa đêm.[15] Justinianos lại lên ngôi một lần nữa phá vỡ truyền thống ngăn ngừa người có khiếm khuyết trị vì đế quốc.[21] Sau khi theo dõi và bắt được những người tiền nhiệm, Leontios và Tiberios bị quân lính xích lại và dẫn đến trình diện Justinianos ở Hippodrome, giờ đang phải mang một cái mũi giả bằng vàng.[22] Tại đây, trước mặt đám đông dân chúng đang giễu cợt, Justinian đặt chân lên cổ Tiberios và Leontios theo một cử chỉ tượng trưng cho sự khuất phục trước khi ra lệnh chặt đầu họ, rồi tới lượt đồng đảng của hai người,[23] cũng như phế truất, chọc mù mắt và trục xuất vị Thượng phụ Kallinikos I thành Constantinopolis đến Roma.[24]